1. Field of the Invention
The present invention relates to a circuit for executing the operations for Euclid mutual division and a processing circuit including this mutual division arithmetic circuit. This processing circuit is used in data error control for telecommunications devices, for example.
2. Description of Related Art
Euclid mutual division is an operation for repeated division using two integers or natural numbers as the initial values. Euclid mutual division is expressed with equation (1), where the initial value of the dividend is a, and the initial value of the divisor is a2. In this equation, xe2x80x98qn . . . amxe2x80x99 is used to express that qn is the quotient and am is the remainder.
a1/a2=q1 . . . a3
a2/a3=q2 . . . a4
a3/a4=q3 . . . a5
.
.
.
anxe2x88x921/an=qnxe2x88x921 . . . an+1xe2x80x83xe2x80x83(1)
This equation can be iterated until the remainder becomes zero.
The following are necessary in order to execute Euclid mutual division with a logic circuit: a dividend storing portion for storing the number to be the dividend, or numerator; a divisor storing portion for storing the number to be the divisor, or denominator; and a computing portion to which the dividend and divisor are input and which computes the remainder. After performing division once, this logic circuit transfers the data stored in the divisor storing portion to the dividend storing portion, transfers the remainder data calculated by the computing portion to the divisor storing portion, and executes division again. The time necessary for these data transfers becomes an issue in reducing the speed of the Euclid mutual division arithmetic.
It is an object of the present invention to provide a Euclid mutual division arithmetic circuit, which can perform the Euclid mutual division operations at high speed, and a processing circuit including this Euclid mutual division arithmetic circuit.
For this reason, the Euclid mutual division arithmetic circuit relating to the first invention in this application comprises: first, second, and third register means for selectively executing a function for computing the Euclid mutual division operations using the divisor and dividend, a function for supplying the divisor used in the Euclid mutual division operations, and a function for supplying the dividend used in the Euclid mutual division operations; (that is, selectively performing the operations, supplying the divisor and supplying the dividend) and means for controlling the first, second, and third register means so that, in the kth operation, the first register means execute the dividend supplying function, the second register means execute the computing function, and the third register means execute the divisor supplying function, and in the (k+1)th operation, the first register means execute the computing function, the second register means execute the divisor supplying function, and the third register means execute the dividend supplying function, and in the (k+2)th operation, the first register means execute the divisor supplying function, the second register means execute the dividend supplying function, and the third register means execute the computing function.
After the first operation is complete, the Euclid mutual division arithmetic circuit relating to the first invention in this application can execute the next operation without transferring data; this circuit can therefore operate at high speeds.
The processing circuit relating to the second invention in this application comprises: a Euclid mutual division arithmetic circuit comprising first, second, and third register means for selectively executing a function for computing the Euclid mutual division using the divisor and dividend, a function for supplying the divisor used in the Euclid mutual division operations, and a function for supplying the dividend used in the Euclid mutual division operations; and means for controlling the first, second, and third register means so that, in the kth operation, the first register means execute the dividend supplying function, the second register means execute the computing function, and the third register means execute the divisor supplying function, and in the (k+1)th operation, the first register means execute the computing function, the second register means execute the divisor supplying function, and the third register means execute the dividend supplying function, and in the (k+2)th operation, the first register means execute the divisor supplying function, the second register means execute the dividend supplying function, and the third register means execute the computing function; as well as a multiplier circuit for multiplying the quotient calculated by this Euclid mutual division arithmetic circuit by a predetermined number.
The processing circuit relating to the second invention in this application can perform the Euclid mutual division operations at high speeds, and can therefore carry out processing at high speeds.